package tianhao.luo.algorithm;

import java.util.Arrays;

/**
 * 普利姆算法实现
 * 1.构造出图
 * 2.构造出最小二叉树
 * @author: tianhao.luo@hand-china.com 2021/7/3  9:17
 */
public class PrimAlgorithm {

    private Graph graph;

    public PrimAlgorithm(Graph graph) {
        this.graph = graph;
    }

    /**
     * 得到最小生成树的算法
     *
     * @param v     表示从图的第几个顶点开始生成
     */
    public void prim(int v) {
        // visited[]标记顶点是否呗访问过
        int[] visited = new int[graph.verxs];
        // visited[]默认元素的值未0,表示没有访问过
        for (int i = 0; i < graph.verxs; i++) {
            visited[i] = 0;
        }
        // 把当前节点标记为已经访问
        visited[v] = 1;
        // h1和h2记录两个顶点的下标
        int h1 = -1;
        int h2 = -1;
        // 将minWeight初始化为大值,用来记录最小值,在遍历过程中会被替换
        int minWeight = Integer.MAX_VALUE;
        // 普利姆算法结束后,会生成verxs-1条边;
        for (int i = 1; i < graph.verxs; i++) {
            // 确定每一次生成的子图,和哪个节点的距离最近
            for (int j = 0; j < graph.verxs; j++) { // 遍历已经访问过的节点(visited[j] == 1)
                for (int k = 0; k < graph.verxs; k++) { // 遍历没有访问过的节点(visited[k] == 0)
                    // 其中graph.weight[j][k] != -1表示节点间是联通的
                    if (visited[j] == 1 && visited[k] == 0 && graph.weight[j][k] != -1 && graph.weight[j][k] < minWeight) {
                        // 替换minWeight,寻找已经访问过的节点和未访问过的节点间的权值最小的边
                        minWeight = graph.weight[j][k];
                        // h1就是为已经访问的节点
                        h1 = j;
                        // h2就是未呗访问的节点
                        h2 = k;
                    }
                }
            }
            // 找到一条最小的边
            System.out.println("边<" + graph.data[h1] + graph.data[h2] + ">权值:" + minWeight);
            // 将当前节点标记为已经访问;为什么是h2?和上面if判断中赋给h2的值有关
            visited[h2] = 1;
            // 本次访问已经结束,重新设置minWeight设置为最大
            minWeight = Integer.MAX_VALUE;
        }

    }

    /**
     * 图
     */
    static class Graph {
        /**
         * 节点个数
         */
        int verxs;
        /**
         * 节点数据
         */
        char[] data;
        /**
         * 边
         */
        int[][] weight;

        public Graph(int verxs) {
            this.verxs = verxs;
            data = new char[verxs];
            weight = new int[verxs][verxs];
        }


        /**
         * 创建图的邻接矩阵
         *
         * @param data   图的各个顶点的值
         * @param weight 图的邻接矩阵
         */
        public void createGraph(char[] data, int[][] weight) {
            for (int i = 0; i < verxs; i++) {
                // 初始化数据
                this.data[i] = data[i];
                // 初始化边
                for (int j = 0; j < verxs; j++) {
                    this.weight[i][j] = weight[i][j];
                }
            }
        }

        /**
         * 展示图的内容
         */
        public void showGraph() {
            for (int i = 0; i < this.weight.length; i++) {
                System.out.println(Arrays.toString(this.weight[i]));
            }
        }
    }
}
